package 二分法;


/**
 * @author： li
 * @date： 2022-01-16 16:11
 * @version 1.0
 */

/*问题描述
　　住在有顶天的天人Tensi对自己的住处很不满。终于有一天她决定把门前碍眼的要石通通丢掉（怒扔要石）。控制要石自然是很容易的事，
   不过也会消耗灵力。假设搬走一块质量为1的要石会消耗1点灵力，而且由于要石都是连着放置的缘故所以每次除了搬走一颗，
   也可以搬走连续的任意数量的要石，自然质量是算在一起的。现在Tensi准备最多使用M次灵力，但是她太懒……所以每次只会使用同量的灵力，
   也因为她太烂，所以也不愿意多花一点灵力……现在很懒的Tensi需要你帮她计算最少一次需要消耗多少灵力，能够在M次内把所有要石都丢到人间去……
输入格式
　　第一行两个数N,M，用一个空格分隔。1<=n<=1000,1<=m<=400
　　表示一共有N颗要石需要搬走已经Tensi最多发动M次灵力。
　　接下来包括N 个正整数 0<=ai<=40000 顺序表示每一颗要石的质量。
输出格式
　　输出一个数T
　　表示Tensi 每次至少消耗T灵力。0<=T<=1000000
　　如果无解输出-1.
样例输入
5 3
1 2 1 1 1
样例输出
3
数据规模和约定
　　对于100%的数据，1<=n<=1000，1<=m<=400，0<=ai<=40000。
　　保证0<=T<=1000000。
思路：
求出次数在m以内 T得最小值
先算出m次时T的值 和1次时T的值
再用二分法求出m次内T的最小值
因为T最小的时候，次数一定是再1到m次的
 */
import java.util.ArrayList;
import java.util.Scanner;
public class 搬走要石01 {
    static int n,m;
    static int count=0;
    static long sum=0;
    static ArrayList<Long> t = new ArrayList<>();
    static boolean panduan(long max, long[] a){
        for (int i=1;i<=n;) {
            sum = sum + a[i];
            i++;
            if(sum>max){
                i=i-1;
                sum=0;
                count++;
            }
            if(sum==max){
                sum=0;
                count++;
            }
        }
//        System.out.println("sum="+sum);
//        System.out.println("max:"+max);
//        System.out.println("原count:"+count);
        //如果剩余的大于max，说明还要取一次
        if(sum!=0){
            if (sum < max) {
                count = count + 1;
            }
        }
//        System.out.println("后count:" + count);
        //次数必须1=<count=<m
        if (count<= m&&count>=1) {
            t.add(max);
            count = 0;
            sum=0;
            return true;
        }
        count=0;
        sum=0;
        return false;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long[] ai,ai2;
        n = sc.nextInt();
        m = sc.nextInt();
        ai = new long[n + 1];
        ai2= new long[n+1];
        ArrayList<Long> res;
        long result = Integer.MAX_VALUE;
        ai[0]=0;
        for (int i = 1; i <=n; i++) {
            ai2[i]=sc.nextInt();
            ai[i]=ai[i-1]+ai2[i];
        }
//        System.out.println(" ");
//        for(int i=1;i<=n;i++){
//            System.out.print(ai2[i]+" ");
//        }
//        System.out.println(" ");
        long l=(ai[n]/m);
        long r=ai[n];
//        System.out.println(l);
//        System.out.println(r);
        while (l+1<r) {
            long mid=(l+r)/2;
//            System.out.println("mid="+mid);
            if(panduan(mid,ai2)){
                r=mid;
            }else
                l=mid;
        }
        res=t;
//        System.out.println(" ");
        if (res.isEmpty()) {
            System.out.println(-1);
        } else {
//            for (long i : res)
//                System.out.print(i + " ");
//            System.out.println(" ");
            for (long i : res) {
                result = Math.min(result, i);
            }
            System.out.println(result);
        }
    }
}
